package com.ssh;

import org.junit.Test;

public class MaxAreaOfIsland_695 {
	private int m, n;
	private int[][] dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
	public int maxAreaOfIsland(int[][] grid) {
		n = grid.length;
		m = grid[0].length;
		int max = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				max = Math.max(max, max(grid, i, j));
			}
		}
		return max;
    }
	
	private int max(int[][] grid, int x, int y) {
		if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == 0) {
			return 0;
		}
		grid[x][y] = 0;
		int z = 1;
		for (int[] d : dir) {
			z += max(grid, x + d[0], y + d[1]);
		}
		return z;
	}
	
	@Test
	public void test() {
		int[][] a = 
				{
				 {0,0,1,0,0,0,0,1,0,0,0,0,0},
				 {0,0,0,0,0,0,0,1,1,1,0,0,0},
				 {0,1,1,0,1,0,0,0,0,0,0,0,0},
				 {0,1,0,0,1,1,0,0,1,0,1,0,0},
				 {0,1,0,0,1,1,0,0,1,1,1,0,0},
				 {0,0,0,0,0,0,0,0,0,0,1,0,0},
				 {0,0,0,0,0,0,0,1,1,1,0,0,0},
				 {0,0,0,0,0,0,0,1,1,0,0,0,0}
				};
		System.out.println(maxAreaOfIsland(a));
	}
}
